import javafx.util.Pair;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1、统计每个单词出现的频率
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        //2、创建一个大小为k的小根堆
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(new Comparator<Pair<String, Integer>>() {
            @Override
            public int compare(Pair<String, Integer> o1, Pair<String, Integer> o2) {
                //如果两个字符串频率相等, 比较两个字符串的字典序
                if(o1.getValue().equals(o2.getValue())){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        //3.让元素依次进入堆
        for (Map.Entry<String, Integer> x : map.entrySet()) {
            heap.add(new Pair<>(x.getKey(), x.getValue()));
            if(heap.size() > k) heap.poll();//弹出堆顶
        }

        //4.返回结果
        List<String> ret = new ArrayList<>();

        while(!heap.isEmpty()){
            ret.add(heap.poll().getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}